/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/5/20 21:31
 */
// 找最长回文子序列
// 区别于子串，子序列不需要连续
public class Solution516 {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len + 1][len + 1];
        for (int i = len - 1; i >= 0; i--) {
            // 需要初始化
            // 首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况
            //所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                // 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
                if (s.charAt(j) == s.charAt(i)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                // 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，
                    // 那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
                // 加入s[j]的回文子序列长度为dp[i + 1][j]。
                    // 加入s[i]的回文子序列长度为dp[i][j - 1]。
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1] ,dp[i + 1][j]);
                }
            }
        }
        return dp[0][len - 1];
    }
}
